package leetcode每日一题;

/**
 * 1. 问题描述(非常经典的一道面试题)
 *   一个数组中只有一个元素出现了一次，其余均是成对出现，找出出现一次的元素
 *
 * 2，算法分析
 *      1. 排序 + 线性扫面   时间复杂度依赖于排序算法的优劣
 *      2. 位运算 ^
 *          注意到题目中说只有一个元素出现一次其余均成对出现即出现2次，实际上敏感一点就会考虑到二进制
 *          运算，所以考虑位运算求解
 *          注意到 ^ 的性值：
 *             0 ^ a = a
 *             a ^ b = b ^ a
 *             a ^ a = 0
 *          利用^扫描一遍数组，最终结果就是出现一次的元素
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 只出现一次的数字 {
    public static void main(String[] args) {

    }

    public int singleNumber(int[] nums) {
        // 注意数组中的数字只有一个元素出现一次，其余全部都出现了2次
        // Arrays.sort(nums);
        int ans = nums[0];
        for(int i = 1; i < nums.length; i++) {
            ans ^= nums[i];
        }
        return ans;
    }
}
